package leetcode.editor.cn.dsa08_hashtable;
//给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
//
// 示例: 
// 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
//输出:
//[
//  ["ate","eat","tea"],
//  ["nat","tan"],
//  ["bat"]
//] 
//
// 说明： 
// 所有输入均为小写字母。
// 不考虑答案输出的顺序。 
// 
// Related Topics 哈希表 字符串 

import java.util.List;
import java.util.*;
public class GroupAnagrams49 {
    public static void main(String[] args) {
        Solution solution = new GroupAnagrams49().new Solution();
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(solution.groupAnagrams(strs));
        // [[bat], [eat, tea, ate], [tan, nat]]
        String[] strs1 = {"",""};
        System.out.println(solution.groupAnagrams(strs1));
        // [["",""]]
        String[] strs2 = {"","b"};
        System.out.println(solution.groupAnagrams(strs2));
        // [["b"],[""]]
        String[] strs3 = {"c","c"};
        System.out.println(solution.groupAnagrams(strs3));
        // [["c","c"]]
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 新建一个映射集合map，遍历数组，每一个字符串生成一个唯一key
         * key存在，则和原value一起存入集合中
         * key不存在，新建key和集合容器，将字符串存入集合中
         */
        public List<List<String>> groupAnagrams(String[] strs) {
            if (strs == null || strs.length == 0) return null;
            Map<String, List<String>> map = new HashMap<>();
            for (String str : strs) {
                // 将字符串转为数组然后排序，再转为字符串作为映射唯一key
                char[] chars = str.toCharArray();
                Arrays.sort(chars);
                String key=String.valueOf(chars);
                // 将字符串存入哈希表中
                if (!map.containsKey(key)) {
                    map.put(key, new ArrayList<>());
                }
                map.get(key).add(str);
            }
            return new ArrayList(map.values());
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}
